/**
 * @copyright Copyright (c) 2024 wzzlyzdn
 * @author    wzzlyzdn (wzzlyzdn@163.com)
 *
 * @file      priority_queue.c
 * @brief     优先队列(堆)
 *
 * @version   V0.01
 * @date      2024-04-30
 *
 */

#include "priority_queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <stdlib.h>

volatile int priority_queue_debug_level = PRIORITYQUEUE_ALL;

#define PRIORITYQUEUE_DEBUG(debug_leval, arg, ...)                                                                      \
    do                                                                                                                  \
    {                                                                                                                   \
        if (priority_queue_debug_level & debug_leval)                                                                   \
        {                                                                                                               \
            fprintf(stdout, "\033[1;%dm[" #debug_leval "]<%s:%4d>[%s]"                                                  \
                            "\033[0m" arg,                                                                              \
                    ((debug_leval == PRIORITYQUEUE_ERROR) ? 31 : 38), __FILE__, __LINE__, __FUNCTION__, ##__VA_ARGS__); \
        }                                                                                                               \
    } while (0)

#define PRT_DEBUG(arg, ...) PRIORITYQUEUE_DEBUG(PRIORITYQUEUE_DEBUG, arg, ##__VA_ARGS__)
#define PRT_ERR(arg, ...) PRIORITYQUEUE_DEBUG(PRIORITYQUEUE_ERROR, arg, ##__VA_ARGS__)

#define PRIORITYQUEUE_ASSERT(mod, cond, ret)                    \
    if (!(cond))                                                \
    {                                                           \
        PRT_ERR("ASSERT failed! module %s, %s\n", #mod, #cond); \
        return (ret);                                           \
    }

#define PRIORITYQUEUE_ASSERT_VOID(mod, cond)                    \
    if (!(cond))                                                \
    {                                                           \
        PRT_ERR("ASSERT failed! module %s, %s\n", #mod, #cond); \
        return;                                                 \
    }

void priority_queue_setdebug_leval(PRIORITYQUEUE_DEBUG_LEVEL level)
{
    PRIORITYQUEUE_ASSERT_VOID(PRIORITYQUEUE_DEBUG_LEVEL, (level >= PRIORITYQUEUE_CLOSE && level <= PRIORITYQUEUE_ALL));
    priority_queue_debug_level = level;
}

PriorityQueue priority_queue_init_private(int capacity, Compare cmp, Swap swap)
{
    PRIORITYQUEUE_ASSERT(capacity, (capacity >= 0), NULL);
    PRIORITYQUEUE_ASSERT(cmp, (NULL != cmp), NULL);
    PRIORITYQUEUE_ASSERT(swap, (NULL != swap), NULL);

    PriorityQueue pq = (PriorityQueue)malloc(sizeof(Heap));
    PRIORITYQUEUE_ASSERT(pq, (NULL != pq), NULL);
    pq->cmp = cmp;
    pq->swap = swap;
    pq->capacity = capacity;
    pq->size = 0;
    pq->data = (Element *)malloc(capacity * sizeof(Element));
    if (NULL == pq->data)
    {
        PRT_ERR("malloc failed\n");
        free(pq);
        return NULL;
    }
    return pq;
}

int priority_queue_empty(PriorityQueue pq)
{
    PRIORITYQUEUE_ASSERT(pq, (NULL != pq), -1);
    return (pq->size == 0);
}

int priority_queue_size(PriorityQueue pq)
{
    PRIORITYQUEUE_ASSERT(pq, (NULL != pq), -1);
    return pq->size;
}

int priority_queue_isfull(PriorityQueue pq)
{
    PRIORITYQUEUE_ASSERT(pq, (NULL != pq), -1);
    return (pq->size >= pq->capacity);
}

int priority_queue_get_element_priority(Element e)
{
    return e.priority;
}

int priority_queue_compare(Element e1, Element e2)
{
    return (priority_queue_get_element_priority(e1) - priority_queue_get_element_priority(e2));
}
void priority_queue_swap(Element *a, Element *b)
{
    PRIORITYQUEUE_ASSERT_VOID(a, (NULL != a));
    PRIORITYQUEUE_ASSERT_VOID(b, (NULL != b));
    Element tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

int get_parent(int index)
{
    return (index - 1) / 2;
}

int get_left_child(int index)
{
    return (2 * index + 1);
}

int get_right_child(int index)
{
    return (2 * index + 2);
}

int priority_queue_insert(PriorityQueue pq, Element e)
{
    PRIORITYQUEUE_ASSERT(pq, (NULL != pq), -1);
    PRIORITYQUEUE_ASSERT(pq, !priority_queue_isfull(pq), -1);

    PRT_DEBUG("insert: id[%d priority[%d t[%ld s[%d\n", e.id, e.priority, e.time, e.status);

    int current = 0;
    pq->data[pq->size++] = e;
    current = pq->size - 1;
    int parent = get_parent(current);

    while (current > 0 && (priority_queue_get_element_priority(pq->data[parent]) > priority_queue_get_element_priority(pq->data[current])))
    {
        pq->swap(&pq->data[parent], &pq->data[current]);
        current = parent;
        parent = get_parent(current);
    }

    return 0;
}

void priority_queue_heapify(PriorityQueue pq, int idx)
{
    if (NULL == pq)
    {
        return;
    }
    int current = idx;

    while (1)
    {
        int left = get_left_child(current);
        int right = get_right_child(current);
        int smallest = current;

        // 检查左子节点
        if (left < pq->size && pq->cmp(pq->data[left], pq->data[smallest]) < 0)
        {
            smallest = left;
        }

        // 检查右子节点
        if (right < pq->size && pq->cmp(pq->data[right], pq->data[smallest]) < 0)
        {
            smallest = right;
        }

        // 如果当前节点是最小值，结束调整
        if (smallest == current)
        {
            break;
        }

        // 交换当前节点与最小值节点
        pq->swap(&pq->data[current], &pq->data[smallest]);
        current = smallest;
    }

    return;
}

Element priority_queue_extract(PriorityQueue pq)
{
    Element e = {0};
    PRIORITYQUEUE_ASSERT(pq, (NULL != pq), e);
    PRIORITYQUEUE_ASSERT(pq, (!priority_queue_empty(pq)), e);

    e = pq->data[0];
    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;
    priority_queue_heapify(pq, 0);
    return e;
}

PriorityQueue priority_queue_init(int capacity)
{
    return priority_queue_init_private(capacity, priority_queue_compare, priority_queue_swap);
}

void priority_queue_destroy(PriorityQueue pq)
{
    PRIORITYQUEUE_ASSERT_VOID(pq, (NULL != pq));
    free(pq->data);
    pq->data = NULL;
    free(pq);
}

int priority_queue_pow(int x, int p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p == 1)
    {
        return x;
    }
    else
    {
        return x * priority_queue_pow(x, p - 1);
    }
}

int heapHeightWithoutMath(int n)
{
    int height = 0;
    while (n > 0)
    {
        n >>= 1; // 相当于将n除以2
        height++;
    }
    return height;
}
int heapLevel(int i)
{
    return (int)(heapHeightWithoutMath(i + 1));
}

int z_space(int mspace, int mleval, int leval)
{
    if (mleval == leval + 1)
    {
        return (mspace * (mleval - leval));
    }
    else
    {
        return (z_space(mspace, mleval, leval + 1) * 2 + 2);
    }
}

int q_space(int mspace, int mleval, int leval)
{
    if (mleval == leval + 1)
    {
        return (0);
    }
    else
    {
        return z_space(mspace, mleval, leval + 1) - 1;
    }
}

int get_element_data(Element ele)
{
    return ele.id;
}
// 打印整个堆的函数
void printHeap(PriorityQueue pq, int size)
{
    PRT_DEBUG("Heap (size %d):\n", size);
    int maxLevel = heapHeightWithoutMath(size);
    int msapec = 4;
    int num = 0;

    for (int l = 0; l < maxLevel; l++)
    {
        int qs = q_space(msapec, maxLevel, l);
        int zs = z_space(msapec, maxLevel, l);
        if (num >= size)
        {
            break;
        }
        for (int i = 0; i < qs; i++)
        {
            printf(" ");
        }

        for (int i = 0; i < priority_queue_pow(2, l); i++)
        {
            if (num >= size)
            {
                break;
            }
            printf("%2d", get_element_data(pq->data[num]));
            for (int p = 0; p < zs; p++)
            {
                printf(" ");
            }
            num++;
        }

        printf("\n");
    }
}
void priority_queue_print(PriorityQueue pq)
{
    PRIORITYQUEUE_ASSERT_VOID(pq, (NULL != pq));
    PRT_DEBUG("------------------------------\n");
    printHeap(pq, pq->size);
    PRT_DEBUG("------------------------------\n");
}

Element init_element(int p)
{
    Element ele;
    ele.id = rand() % 100;
    ele.priority = p;
    ele.status = 1;
    ele.time = time(NULL);
    return ele;
}
void priority_queue_test_main(void *arg)
{
    printf("%ld\n\n", sizeof(Compare));

    PRT_DEBUG("PRT_DEBUG TEST\n");
    PRT_ERR("PRT_ERR TEST\n");
    PRT_DEBUG("sizeof(Heap) = [%lu]\n", sizeof(Heap));
    PRT_DEBUG("sizeof(Element) = [%lu]\n", sizeof(Element));
    PRT_DEBUG("main: priority_queue_init\n");
    PriorityQueue pq = priority_queue_init(15);
    PRIORITYQUEUE_ASSERT_VOID(pq, (NULL != pq));

    srand(time(NULL));
    int i = 10;
    while (!priority_queue_isfull(pq))
    {
        priority_queue_insert(pq, init_element(rand() % 10));
    }
    for (int i = 0; i < pq->size; i++)
    {
        printf("%d ", get_element_data(pq->data[i]));
    }
    printf("\n");

    priority_queue_print(pq);

    Element e;

    while (!priority_queue_empty(pq))
    {
        e = priority_queue_extract(pq);
        printf("[%d], %d\n", priority_queue_get_element_priority(e), get_element_data(e));
    }

    priority_queue_destroy(pq);
    priority_queue_destroy(NULL);

    return ;
}